The present invention relates to a binary adder, and in particular to a multiple carry skip adder.
A binary adder having multiple, 1024 to 2048, bits must be operated at high speed in order to process RSA encryption rapidly. However, according to a conventional technique, to be described below, the speed at which a binary adder can be operated is limited by a carry signal transmitted from a lower level, and a desirable operating speed can not be acquired. The conventional technique will now be described.
(1) Ripple Carry System
A ripple adder comprises parallel arranged full adders whose number is equivalent to that of the bits. But while a circuit required for a ripple carry system is not complicated, the maximum gate delay is equivalent to the total of the gate delays of the bits involved, and it is therefore very difficult to ensure a desirable operating speed.
(2) Carry Monitoring System
Since the maximum gate delay of the ripple adder is the maximum N stages for N bits, an ensured operating speed is reduced in inverse proportion to the number of bits. However, since the transfer of a carry is required only when two values, X and Y, to be added together are exclusively 1 and when a carry is transmitted from a lower level, these conditions are rarely sequential. For 1024 bits, as it is calculated that the above conditions happen for at most 11 sequential bits, the average operating speed is anticipated to be 100 times the ensured operating speed. In this system, a carry monitoring circuit is additionally provided to enter a waiting time when carries occur continuously. The carry monitoring system, however, requires a large circuit, and will increase power consumption and potentially will destabilize the operation.
(3) Carry Skip System
A binary adder is divided into several blocks to perform the addition in individual blocks, and a +1 compensation by a carry signal from a lower level. A binary adder according to this system is called a carry skip adder. Although it has a complicated circuit, the carry skip system requires only a small amount of power, and its operation is stable. The circuit for this system is more complicated than the ripple adder, and is as complicated as the adder for the carry monitor system.
In a one-stage carry step system, for the addition of N bits, n such that Nxe2x89xa6n(n+2)/2+2 is acquired and (n+3) is a gate delay for n. For 1024 bits, N=1024 and n=45, i.e., a gate delay of 48 is obtained.
The carry skip system is described in, for example, Information Processing, Vol. 37, No. 1 pp. 80-85, Information Processing Institute, January 1996.
Furthermore, two-stage carry skip adder is described in IBM Technical Disclosure Bulletin Vol. 27, No. 11, April 1985, pp. 6785-6787. Since a binary adder is divided into blocks symmetrically, the operating speed is high for a small number of bits, but as the effect of skipping carries is reduced when handling a lot of bits, the operating speed becomes relatively slower.
It is, therefore, one object of the present invention to provide a binary adder that has two or more carry-skipped stages to enable a higher operating speed.
It is another object of the present invention to provide a high-speed multiplier that employs the carry skip adder.
An N-stage carry skip adder (Nxe2x89xa73), which is a first form of the present invention, includes a plurality of ripple adders, wherein at least one part of the plurality of ripple adders is divided into a plurality of groups. A carry signal is transferred from one group to one upper group, and if a group includes a plurality of ripple adders, a carry signal is transferred between ripple adders in the group. In addition, a circuit for calculating C=C2+F*C1 is included, wherein the C1 denotes a carry signal from the one group to the one upper group, and the F denotes a signal indicating whether or not outputs of all adders in the one upper group are 1s, and the C2 denotes a carry signal associated with the most upper ripple adder in the one upper group.
Furthermore, if a group includes three or more ripple adders, the three or more ripple adders are organized into a plurality of groups at Nxe2x88x922 levels, the N-stage carry skip adder further comprises: a circuit for calculating C21=C4+F20*C30; and a circuit for calculating C2n+1=C2n+F2n*C3n, wherein 1xe2x89xa6nxe2x89xa6Nxe2x88x922, and C2Nxe2x88x921=C2, and said C30 denotes a carry signal transferred to the most upper ripple adder from a ripple adder in a group at a level 1 to which the most upper ripple adder belongs, and the level 1 is the lowest level, and the C3n (1xe2x89xa6nxe2x89xa6Nxe2x88x922) denotes a carry signal transferred to a group at a level n to which the most upper ripple adder belongs from an adjacent group at the level n, and the C4 denotes a carry signal of the most upper ripple adder, and the F20 denotes a signal indicating whether or not outputs of all adder in the most upper ripple adder are 1s, and the F2n denotes a signal indicating whether or not outputs of all adders upper than a ripple adder associated with a circuit outputting said C3n and up to the most upper ripple adder are 1s.
By this configuration, the three or more-stage carry skip adder of the present invention can reduce a lot of gate delay. The carry signal is only transmitted to a upper adder, is never returned to a lower adder. In the three-stage carry skip adder, a plurality of ripple adders are further organized into groups at one level in addition to the primary grouping, and a circuit for calculating C21=C4+F20*C30 and a circuit for calculating C22=C2=C21+F21*C31 are included. In the four-stage carry skip adder, a plurality of ripple adders are further organized into groups at two levels in addition to the primary grouping, a circuit for calculating C21=C4+F20*C30, and a circuit for calculating C22=C21+F21*C31, and a circuit for calculating C23=C2=C4+F22*C32 are included. The first form of the present invention indicates, for example, in FIG. 3, a set of AND circuit 435 and OR circuit 437, a set of AND circuit 441 and OR circuit 443, and a set of AND circuit 445 and OR circuit 447.
C=C2+F*C1, C21=C4+F20*C30 and C2n+1=C2=C2n+F2n*C3n mean that a carry signal of a specific adder is generated when a carry is generated by the specific adder, or when all adders of a block including the specific adder have outputs of 1 and a carry is forwarded from a preceding block.
In the first form of the present invention, there is a phrase xe2x80x9cone part of the plurality of ripple addersxe2x80x9d because a simple ripple adder or an adder in a different system may be additionally provided at a lower or an upper level of the above configured carry skip adder. Particularly, in an adder used in a multiplier, a modified circuit of the present invention, that deals with two types of carries independently generated, is connected to the lower level of the adder of the present invention.
The number of ripple adders in the one upper group may be equal to or more than that of ripple adders in the one group. Therefore, even if the number of bits becomes large, the speed of the addition can be enhanced.
A carry skip adder, which is a second form of the present invention, includes a plurality of carry skip adders, and at least one part of the plurality of ripple adders is divided into a plurality of groups, and a carry signal is transferred from one group to one upper group. The carry skip adder further comprises a circuit for calculating C=C2+F*C1, wherein the C1 denotes a carry signal from the one group to the one upper group, and the F denotes a signal indicating whether or not outputs of all adders in the one upper group are 1s, and the C2 denotes a carry signal associated with the most upper ripple adder in the one upper group. In addition, if a group includes a plurality of ripple adders, a carry signal is transferred between ripple adders in the group, a circuit for calculating C2=C4+F21*C31 is included, wherein the C31 denotes a carry signal associated with a ripple adder one lower than the most upper ripple adder, and the C4 denotes a carry signal of the most upper ripple adder, and the F21 denotes a signal indicating whether or not outputs of all adders in the most upper ripple adder are 1s. The two-stage carry skip adder of the second form of the present invention can reduce a lot of gate delay. The carry signal is only transferred to the upper adder, is never returned to the lower adder. For example, in FIG. 1, a circuit for calculating C=C2+F*C1 is a set of AND circuit 71 and OR circuit 73, and a circuit for calculating C2=C4+F21*C31 is a set of AND circuit 67 and OR circuit 69. Note that in FIG. 1, a ripple adder including a half adder 11 and a full adder 13 and a ripple adder including a half adder 15 and a full adder 17 are organized into one group. Since this group includes two ripple adders, two carry signals exists, one transferred between groups, the other transferred within the group.
The second form of the present invention comprises: a circuit for EX-ORing the C and an output S0 of the lowest adder in the lowest ripple adder in a group one upper than the one upper group; and a circuit for EX-ORing the logical multiplication of the C and the S0 and an output S1 of an adder one upper than the lowest adder. The outputs of these exclusive OR (EX-OR) are a final output of the lowest adder and a final output of the adder one upper than the lowest adder, respectively.
A carry skip adder, which is a third form of the present invention, comprises: a plurality of ripple adders, wherein at least a part of the plurality of ripple adders comprises: a first ripple adder; a second ripple adder one lower than the first ripple adder; a circuit for calculating C2=C1+F1*C0 if a carry signal C0 with respect to the second ripple adder is delivered to the first ripple adder, wherein said C1 denotes a carry signal of the first ripple adder, and said F1 denotes a signal indicating whether or not all outputs in the first ripple adder are 1s; a third ripple adder two or more lower than the first ripple adder. If a carry signal C with respect to the third ripple adder is delivered from a circuit associated with the third ripple adder to the first ripple adder, a circuit for calculating C3=C2xe2x80x2+F2*C is included, wherein said F2 denotes a signal indicating whether or not all outputs of ripple adders from a ripple adder one higher than the third ripple adder to the first ripple adder are 1s, and a carry signal C2xe2x80x2 is associated with the first ripple adder. The multiple-stage carry skip adder of the third form of the present invention can reduce a lot of gate delay. The carry signal is only delivered to the upper adder, is never returned to the lower adder. For example, if the first ripple adder is a set of adder 23 and 25 in FIG. 1, a circuit for calculating C2=C1+F1*C0 is a set of AND circuit 97 and OR circuit 103, and a circuit for calculating C3=C2xe2x80x2+F2*C is a set of AND circuit 101 and OR circuit 105.
If the C3 associated with the first ripple adder is outputted, a circuit for EX-ORing the C3 and an output S0 of the lowest adder in a fourth ripple adder one upper than the first ripple adder and a circuit for EX-ORing the logical multiplication of the C3 and the S0 and an output S1 of an adder one upper than the lowest adder are included. If the C3 associated with the first ripple adder is not outputted, a circuit for EX-ORing the C2 and an output S0 of the lowest adder in the fourth ripple adder and a circuit for EX-ORing the logical multiplication of the C2 and the S0 and an output S1 of an adder one upper than the lowest adder are included. These outputs of the exclusive OR (EX-OR) circuits are a final output of the lowest adder in the fourth ripple adder and a final output of the adder one upper than the lowest adder, respectively. For example, if the first ripple adder is a set of a half adder 15 and a full adder 17 in FIG. 1, the C3 is provided to the fourth ripple adder including a half adder 19 and a full adder 21. If the first ripple adder is a set of the half adder 19 and the full adder 21, the C2 is provided to a set of a half adder 23 and a full adder 25 (the fourth ripple adder).
If the fourth ripple adder includes three or more adders, a circuit for EX-ORing an output Sm of an adder m (mxe2x89xa73) upper than the lowest adder and the logical multiplication of the C3 and outputs of all adders from the lowest adder to an adder mxe2x88x921 upper than the lowest adder is included. For example, if the first ripple adder is a set of a half adder 471 and a full adder 473 in FIG. 4, the fourth ripple adder is a set of a half adder 475 and full adders 477 and 479, and includes three adders. Then, the final output of the full adder 479 is exclusive OR of the output of the full adder 479 and the logical multiplication of outputs of adder 475 and 477 and the C3.
A carry skip adder, which is a fourth form of the present invention, comprises a plurality of ripple adders, wherein at least one part of the plurality of ripple adders is divided into a plurality of groups, and a carry signal is transferred from one group to one upper group. In addition, a circuit for calculating C=C2+F*C1 is included, wherein the C1 denotes a carry signal from the one group to the one upper group, and the F denotes a signal indicating whether or not outputs of all adders in the one upper group are 1s, and the C2 denotes a carry signal associated with the most upper ripple adder in the one upper group. In a group including two or more ripple adders, a plurality of ripple adders in the group are organized into a plurality of sub-groups, and a carry signal is transferred from one sub-group to one upper sub-group, a circuit for calculating C5=C4+F1*C3 is included, wherein the C3 denotes a carry signal from the one sub-group to the one upper sub-group, and the F1 denotes a signal indicating whether or not outputs of all adder in the one upper sub-group are 1s, and the C4 denotes a carry signal associated with the most upper ripple adder in the one upper sub-group. The group may have only one ripple adder, and the sub-group may have more sub-groups. For example, in FIG. 4, adders 451 through 479 are organized into one group, and adders 451 through 465 are organized into a first sub-group, and adders 467 through 479 are organized into a second sub-group. In addition, the first sub-group is divided into two sub-group, adders 451 through 457 and adders 459 through 465. The second sub-group is divided into three sub-groups, adders 467 and 469, adders 471 and 473, and adders 475 through 479. The two sub-groups in the first sub-group is divided into sub-groups each having only one ripple adder.
A modified carry skip adder of the first through fourth forms of the present invention comprises: a plurality of ripple adders, wherein an input of a least significant adder in at least a part of the plurality of ripple adders is three bits, and the part of the plurality of ripple adders comprises: a circuit for adding F1*C0 and C1 and F2 if a carry signal C0 with respect to an adder one lower than the least significant adder is transmitted to one ripple adder including the least significant adder, wherein C1 denotes a carry signal of the one ripple adder, and F1 denotes a signal indicating whether or not all outputs in the one ripple adder are 1, and F2 denotes a least significant output of a ripple adder one higher than the one ripple adder. Since two types of carries are independently generated, an addition circuit (a full adder) is employed.
For the two-stage carry skip adder, each of N-bit inputs are divided, from a lower level, into a first group having three bits, a second group having two bits, a third group having two 2-bit sets, and a fourth and following groups, wherein an n-th group (n is an integer of 4 or more) has nxe2x88x921 sets, and in the n-th group, a first and a second set in the n-th group has two bits each, and an m-th set (m is an integer of 3 or more) has m bits. The two-stage carry skip adder comprises N adders. Each adder is connected to two input at the same bit positions of the two N-bit inputs. A ripple carry is directly transmitted from an adder to a succeeding adder in the first and second groups and in each said set. By this, ripple adders divided into a plurality of blocks are arranged. In addition, two skipped carries are forwarded by a line for transmitting a carry from a set to a succeeding set in each the group of the third group and following groups and a line for transmitting a carry from a group to a succeeding group in each the group of the second group and following groups. Finally, a circuit for correcting the result of the addition by using a transmitted carry and the output of said adder is provided. The number of the circuit is not limited to one, is typically plural. The feature of the adder is the division of ripple adders into blocks.
For a three-stage carry skip adder, each of two N-bit inputs is divided into, from a lower level, a first class having three bits, a second class having two bits, a third class having two 2-bit groups, a fourth class having a first group having two 2-bit sets and a second group having two 2-bit sets, a fifth class having a first group having two 2-bit sets, a second group having two 2-bit sets and a third group having two 2-bit sets and a 3-bit set, a sixth and following classes, wherein an n-th class (n is an integer of 6 or more) has nxe2x88x922 groups, and in the n-th class, a first and second and third groups are the same as the respective groups in the fifth class, and a g-th group (g is an integer of 4 or more) has g sets, and in the g-th group, a first set has two bits and an s-th set (s is an integer of 2 or more) has s bits. The three-stage carry skip adder comprises N adders. Each of the adder is connected to two input at the same bit positions of the two N-bit inputs. A ripple carry is directly transmitted from an adder to a succeeding adder in the first and second classes and in each group of the third class, and in each set. By this, ripple adders divided into a plurality of blocks are arranged. In addition, three skipped carries are forwarded by a line for transmitting a carry from a set to a next set in each group of the third and following classes, and a line for transmitting a carry from a group to a next group in each class of the fourth and following classes and a line for transmitting a carry from a class to a next class in each class of the second and following classes. Finally, a circuit for correcting the result of the addition by using a transmitted carry and the output of the adder is provided.
For a four-stage carry skip adder, each of two N-bit inputs is divided into, from a lower level, a first block having three bits, a second block having two bits, a third block having two 2-bit sets, a fourth block having two classes each comprising two groups composed of two 2-bit sets each, a fifth and following blocks, wherein an b-th block (b is an integer of 5 or more) has bxe2x88x922 classes, and in the b-th block, classes up to a bxe2x88x923-th class are the same as corresponding classes in the previous block, and a bxe2x88x922-th class has bxe2x88x922 groups, and in bxe2x88x922-th class, a first group has two 2-bit sets, a second group has two 2-bit sets and a g-th group (g is an integer of 3 or more) has g sets, and in the g-th group, a first set has two bits and an s-th set (s is an integer of 2 or more) has s bits.
Each of N adders is connected to two input at the same bit positions of said two N-bit inputs. A ripple carry is directly transmitting from an adder to a succeeding adder in the first and the second blocks and in each set of the third and following blocks. This is a ripple adder divided into blocks. Three skipped carries are forwarded by a line for transmitting a carry from a set to a succeeding set in the third block and in each group of the fourth and following blocks, and a line for transmitting a carry from a group to a succeeding group in each class of the fourth and following blocks, and a line for transmitting a carry from a class to a succeeding class in each of the fourth and following blocks, and a line for transmitting a carry from a block to a succeeding block in each of the second and following blocks. Finally, a circuit for correcting the result of the addition by using a transmitted carry and the output of the adder is provided.